package 左哥算法.ch03堆;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;

/**
 * dj斯特拉堆
 * todo：加上最短路径方案数
 */
public class NodHeap<T> {
    private Map<T, Integer> indexMap;
    private Map<T, Integer> pathMap;    //记录最短路径条数
    private Map<T, T> preMap;       //记录上一个节点
    private T[] heap;
    private int heapSize = 1;
    private MyComparator<T> comparator;
    private MyUpdater<T> updater;

    /**
     * node:原节点
     * info:走另一条路线的信息
     */
    public void addOrUpdateOrIgnore(T node, T info, T pre) {
        Integer i = indexMap.get(node);
        if (i != null) {    //堆中存在node的情况
            if (comparator.compare(node, info)) {    //是否需要更新
                insert(node,info,pre,i);
                sink(i);
            }
            return;
        }
        insert(node,info,pre,heapSize++);
    }

    /**
     * 更新node的索引、前缀、以及信息
     */
    public void insert(T node,T info,T pre,int i){
        heap[i]=node;
        indexMap.put(node,i);
        preMap.put(node,pre);
        updater.update(node,info);
        rise(i);
    }
        public T pop() {
            T pop = heap[1];
            swap(1, --heapSize);
            sink(1);
            return pop;
        }
    public NodHeap(int size) {
        indexMap = new HashMap<>(size);
        pathMap = new HashMap<>(size);
        preMap = new HashMap<>(size);
        this.heap = (T[]) new Object[size + 1];   //0位置弃而不用
    }

    public void swap(int a, int b) {
        T node = heap[a];
        heap[a] = heap[b];
        heap[b] = node;
        indexMap.put(heap[a], a);
        indexMap.put(heap[b], b);
    }

    /**
     * 从指定位置向上升起
     */
    public void rise(int i) {
        while (i != 1) {  //不是根节点
            int parent = i >> 1;
            if (!comparator.compare(heap[parent], heap[i])) {   //无需上升
                break;
            }
            swap(parent, i);
            i = parent;
        }
    }

    /**
     * 从指定位置向下沉
     */
    public void sink(int i) {
        while (!isLeaf(i)) {     //并非叶子节点
            int child = topChild(i);
            if (!comparator.compare(heap[i], heap[child])) {   //当前节点是最小的，无需下沉
                break;
            }
            swap(i, child);
            i = child;
        }
    }

    public int topChild(int i) {
        int l = i << 1;
        int r = i << 1 | 1;
        if (r >= heapSize) {
            return l;
        }
        if (comparator.compare(heap[l], heap[r])) {
            return r;
        }
        return l;
    }

    public boolean isLeaf(int i) {
        return i << 1 >= heapSize;
    }

    public LinkedList<T> preList(T o) {
        LinkedList<T> list = new LinkedList<>();
        while (o != null) {
            list.addFirst(o);
            o = preMap.get(o);
        }
        return list;
    }
    public boolean isNotEmpty(){
        return heapSize>1;
    }

    public void setUpdater(MyUpdater<T> updater) {
        this.updater = updater;
    }

    public void setComparator(MyComparator<T> comparator) {
        this.comparator = comparator;
    }

    public interface MyComparator<T> {
        /**
         * 返回true需要更新，false无需更行
         * @param old
         * @param young
         * @return
         */
        boolean compare(T old, T young);
    }

    public interface MyUpdater<T> {
        void update(T old, T young);
    }
}
